package array;

import org.junit.Test;

import java.util.Arrays;

public class CanJump55 {

    @Test
    public void test() {
        canJump(new int[]{2,3,1,1,4});
        canJump(new int[]{3,2,1,0,4});
        canJump(new int[]{0});
        canJump(new int[]{0,2,3});

        canJump2(new int[]{2,3,1,1,4});
        canJump2(new int[]{3,2,1,0,4});
        canJump2(new int[]{0});
        canJump2(new int[]{0,2,3});
    }

    //解法2: 直接计算能跳到的最远位置
    public boolean canJump2(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return true;
        }
        // 在当前位置能跳到的最远距离
        int maxIndex = 0;
        for (int i = 0; i < nums.length-1; i++) {
            int curMaxIndex = i + nums[i];
            if (curMaxIndex > maxIndex) {
                maxIndex = curMaxIndex;
            }
            if (maxIndex <= i) {
                // 遇到0, 没法往前了
                System.out.format("nums: %s, canJump: %s\n", Arrays.toString(nums), false);
                return false;
            }
            if (maxIndex >= nums.length-1) {
                System.out.format("nums: %s, canJump: %s\n", Arrays.toString(nums), true);
                return true;
            }
        }
        return false;
    }

    //解法1: 从尾到头计算是否能跳到
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return true;
        }
        boolean[] can = new boolean[nums.length];
        for (int i = nums.length-2; i >= 0; i--) {
            can[i] = false;
            for (int j = nums[i]; j >= 1; j--) {
                if (i + j >= nums.length-1) {
                    can[i] = true;
                    break; // 不需要计数, 只需要判断是否可达
                } else if (can[i+j]) {
                    can[i] = true;
                    break;
                }
            }
        }
        System.out.format("nums: %s, canJump: %s\n", Arrays.toString(nums), can[0]);
        return can[0];
    }
}
